package simple;

import java.util.HashMap;

/**
 * 13. 罗马数字转整数
 * 示例 1:
 *
 * 输入: "III"
 * 输出: 3
 * 示例 2:
 *
 * 输入: "IV"
 * 输出: 4
 * 示例 3:
 *
 * 输入: "IX"
 * 输出: 9
 * 示例 4:
 *
 * 输入: "LVIII"
 * 输出: 58
 * 解释: L = 50, V= 5, III = 3.
 * 示例 5:
 *
 * 输入: "MCMXCIV"
 * 输出: 1994
 * 解释: M = 1000, CM = 900, XC = 90, IV = 4.
 * */
public class RomanToInt {

    /**
     * 时间复杂度： O(n) 空间复杂度：O(1)
     * 思路：通过观察发现，如果小值出现在左边就是减去该值 比如IV = 0 - 1 + 5 = 4
     * 所以每次判断当前值是否比上一次的值大就可以绝对是否加减
     * */
    public int romanToInt(String s){
        int preValue = getValue(s.charAt(0));
        int result = 0;
        for (int i = 1; i < s.length(); i++) {
            if(preValue < getValue(s.charAt(i))){
                result -= preValue;
            }else {
                result += preValue;
            }
            preValue = getValue(s.charAt(i));
        }
        return result + preValue;
    }

    // 获取值
    public int getValue(char c){
        switch (c){
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }

    // 新奇的思路 时间复杂度:O(n) 空间复杂度：O(1)
    /**
     * 思路 我们首先加上第一个罗马文对应的值，然后再判断第一个和第二个字符
     * 是不是属于hash中存在的罗马文，如果存在加上对应的值
     *
     * 为什么减IV = 3？
     * 因为我们首先加上了I 再加上IV 就等于 IV本身的值4
     * 比如 result = 0; 第一步加上了I 变成了1 ，然后我们在循环中指向下一个字符V，这时
     * 需要把IV结合去判断在hash中是否存在，很显然是存在的，所以我们加上3 变成4.
     *
     *
     * */
    public int romanToInt1(String s){
        HashMap<String, Integer> m = new HashMap<String, Integer>(){{
            put("I", 1);
            put("IV", 3);
            put("IX", 8);
            put("V", 5);
            put("X", 10);
            put("XL", 30);
            put("XC", 80);
            put("L", 50);
            put("C", 100);
            put("CD", 300);
            put("CM", 800);
            put("D", 500);
            put("M", 1000);
        }};
        int result = m.get(s.substring(0,1));
        for (int i = 1; i < s.length(); i++) {
            String one = s.substring(i, i+1);
            String two = s.substring(i-1, i+1);
            // 判断两个字符的在hashMap集合中是否存在
            if(m.containsKey(two)){
                result += m.get(two);
            }else{
                result += m.get(one);
            }

        }

        return result;
    }


    // main
    public static void main(String[] args) {
        RomanToInt rti = new RomanToInt();
        int i = rti.romanToInt1("MCMXCIV");
        System.out.print(i);
    }
}
